This invention relates generally to communicating data in a secure fashion, and more particularly to a cryptographic system and methods using public key cryptography.
Computer systems are found today in virtually every walk of life for storing, maintaining, and transferring various types of data. The integrity of large portions of this data, especially that portion relating to financial transactions, is vital to the health and survival of numerous commercial enterprises. Indeed, as open and unsecured data communications channels for sales transactions gain popularity, such as credit card transactions over the Internet, individual consumers have an increasing stake in data security.
Thus, for obvious reasons, it is important that financial transaction communications pass from a sender to an intended receiver without intermediate parties being able to interpret the transferred message.
Cryptography, especially public key cryptography, has proven to be an effective and convenient technique of enhancing data privacy and authentication. Data to be secured, called plaintext, is transformed into encrypted data, or ciphertext, by a predetermined encryption process of one type or another. The reverse process, transforming ciphertext into plaintext, is termed decryption. Of particular importance to this invention is that the processes of encryption and decryption are controlled by a pair of related cryptographic keys. A “public” key is used for the encryption process, and a “private” key is used to decrypt ciphertext. The public key transforms plaintext to ciphertext, but cannot be used to decrypt the ciphertext to retrieve the plaintext therefrom.
As an example, suppose a Sender A wishes to send message M to a recipient B. The idea is to use public key E and related private key D for encryption and decryption of M. The public key E is public information while D is kept secret by the intended receiver. Further, and importantly, although E is determined by D, it is extremely difficult to compute D from E. Thus the receiver, by publishing the public key E, but keeping the private key D secret, can assure senders of data encrypted using E that anyone who intercepts the data will not be able to decipher it. Examples of the public key/private key concept can be found in U.S. Pat. Nos. 4,200,770, 4,218,582, and 4,424,414.
The prior art includes a number of public key schemes, in addition to those described in the above-identified patents. Over the past decade, however, one system of public key cryptography has gained popularity. Known generally as the “RSA” scheme, it is now thought by many to be a worldwide defacto standard for public key cryptography. The RSA scheme is described in U.S. Pat. No. 4,405,829 which is fully incorporated herein by this reference.
The RSA scheme capitalizes on the relative ease of creating a composite number from the product of two prime numbers whereas the attempt to factor the composite number into its constituent primes is difficult. The RSA scheme uses a public key E comprising a pair of positive integers n and e, where n is a composite number of the formn=p·q  (1)where p and q are different prime numbers, and e is a number relatively prime to (p−1) and (q−1); that is, e is relatively prime to (p−1) or (q−1) if e has no factors in common with either of them. Importantly, the sender has access to n and e, but not to p and q. The message M is a number representative of a message to be transmitted wherein0≦M≦n−1.  (2)The sender enciphers M to create ciphertext C by computing the exponentialC≡Me (mod n).  (3)
The recipient of the ciphertext C retrieves the message M using a (private) decoding key D, comprising a pair of positive integers d and n, employing the relationM≡Cd (mod n)  (4)As used in (4), above, d is multiplicative inverse ofe(mod(lcm((p−1), (q−1))))  (5)so thate·d≡1(mod(lcm(p−1), (q−1))))  (6)where lcm((p−1), (q−1)) is the least common multiple of numbers p−1 and q−1. Most commercial implementations of RSA employ a different, although equivalent, relationship for obtaining d:d≡e−1mod((p−1) (q−1)).  (7)This alternate relationship simplifies computer processing.
Note: Mathematically (6) defines a set of numbers and (7) defines a subset of that set. For implementation, (7) or (6) usually is interpreted to mean d is the smallest positive element in the set.)
The net effect is that the plaintext message M is encoded knowing only the public key E (i.e., e and n). The resultant ciphertext C can only decoded using decoding key D. The composite number n, which is part of the public key E, is computationally difficult to factor into its components, prime numbers p and q, a knowledge of which is required to decrypt C.
From the time a security scheme, such as RSA, becomes publicly known and used, it is subjected to unrelenting attempts to break it. One defense is to increase the length (i.e., size) of both p and q. Not long ago it was commonly recommended that p and q should be large prime numbers 75 digits long (i.e., on the order of 1075). Today, it is not uncommon to find RSA schemes being proposed wherein the prime numbers p and q are on the order of 150 digits long. This makes the product of p and q a 300 digit number. (There are even a handful of schemes that employ prime numbers (p and q) that are larger, for example 300 digits long to form a 600 digit product.) Numbers of this size, however, tend to require enormous computer resources to perform the encryption and decryption operations. Consider that while computer instruction cycles are typically measured in nanoseconds (billionths of seconds), computer computations of RSA steps are typically measured in milliseconds (thousandths of seconds). Thus millions of computer cycles are required to compute individual RSA steps resulting in noticeable delays to users.
This problem is exacerbated if the volume of ciphertext messages requiring decryption is large—such as can be expected by commercial transactions employing a mass communication medium such as the Internet. A financial institution may maintain an Internet site that could conceivably receive thousands of enciphered messages every hour that must be decrypted, and perhaps even responded to. Using larger numbers to form the keys used for an RSA scheme can impose severe limitations and restraints upon the institution's ability to timely respond.
Many prior art techniques, while enabling the RSA scheme to utilize computers more efficiently, nonetheless have failed to keep pace with the increasing length of n, p, and q.
Accordingly, it is an object of this invention to provide a system and method for rapid encryption and decryption of data without compromising data security.
It is another object of this invention to provide a system and method that increases the computational speed of RSA encryption and decryption techniques.
It is still another object of this invention to provide a system and method for implementing an RSA scheme in which the factors of n do not increase in length as n increases in length.
It is still another object to provide a system and method for utilizing multiple (more than two), distinct prime number factors to create n.
It is a further object to provide a system and method for providing a technique for reducing the computational effort for calculating exponentiations in an RSA scheme for a given length of n.